#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:

    int LIS(vector<int>& a) {
        int n = a.size();
        if (n == 0)return 0;
        vector<int> dp;
        dp.push_back(a[0]);
        for (int i = 1; i < n; i++) {
            if (a[i] > dp.back()) {
                dp.push_back(a[i]);
            }
            else {
                int l = -1;
                int r = dp.size();
                while (l + 1 != r) {
                    int mid = (l + r) >> 1;
                    if (dp[mid] > a[i])r = mid;
                    else l = mid;
                }
                if (r >= 0 && r < dp.size()) {
                    // cout<<"iii"<<r<<endl;
                    dp[r] = a[i];
                }

            }
            // cout<<dp.size()<<endl;
        }

        return dp.size();
    }
};